def puzzle_solver(pieces, width, height):
    map = {}  #存储碎片之间的映射关系，方便直接找到对应碎片下面的碎片
    top_pieces = []  #上边框碎片集合
    for p in pieces:
        if p[0] != (None, None):
            map[(p[0])] = p
        else:
            top_pieces.append(p)
    tl_corner = [p for p in top_pieces if p[1][0] == None][0]  #左上角碎片
    top_border = [tl_corner]
    clue = tl_corner[1][1]
    res = []  #store the final result
    first = [tl_corner[2]]
    for i in range(width - 1):
        next_piece = [p for p in top_pieces if p[1][0] == clue][0]
        first.append(next_piece[2])
        clue = next_piece[1][1]
        top_border.append(next_piece)
    res.append(tuple(first))
    last_row = top_border
    for i in range(height - 1):
        next_row = []
        ids = []
        for x in last_row:
            next_piece = map[x[1]]
            next_row.append(next_piece)
            ids.append(next_piece[2])
            last_row = next_row
        res.append(tuple(ids))
    return res